# 寻找左边界
def binary_search(nums: list[int], target: int):
    left = 0
    right = len(nums)
    # 二分查找
    while left < right:
        # 防止溢出bug
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid

    # target比所有数都大
    if left == len(nums):
        return -1
    # target比所有数都小
    if nums[left] != target:
        return -1
    return left


if __name__ == '__main__':
    nums = [2, 2, 4, 5, 6, ]
    print(binary_search(nums, 2))
    print(binary_search(nums, 1))
    print(binary_search(nums, 22))
    print(binary_search(nums, 4))
